#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <string>
#define _clr(x,a) memset(x,a,sizeof(x))
using namespace std;
const int N=120;
const int INF=0x3f3f3f3f;
int t,x,y;
string mp[N];
int g[N][N];
bool vis[N][N];
bool used[N];
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int low[N];
int cnt;
int c[N][N];
struct node{
    int i;
    int j;
    int s;
    node(int _i,int _j,int _s):i(_i),j(_j),s(_s){}
};
void init(){
    _clr(g,INF);
    for(int i=0;i<N;i++){
        mp[i]="";
    }
    _clr(c,0);
}
//以(i,j)为起点bfs
void bfs(int i,int j){
    int tidx=c[i][j];
    queue<node> que;
    que.push(node(i,j,0));
    vis[i][j]=true;
    while(!que.empty()){
        node tmp=que.front();
        que.pop();
        int ti=tmp.i;
        int tj=tmp.j;
        int ts=tmp.s;
        //printf("%d %d %d\n",ti,tj,ts);
        for(int i=0;i<4;i++){
            int tti=ti+dir[i][0];
            int ttj=tj+dir[i][1];

            if(tti<0 || tti>y || ttj<0 || ttj>x || vis[tti][ttj] || mp[tti][ttj]=='#'){
                continue;
            }
            //printf("----%d %d %c\n",tti,ttj,mp[tti][ttj]);

            que.push(node(tti,ttj,ts+1));
            vis[tti][ttj]=true;
            if(mp[tti][ttj]=='S' || mp[tti][ttj]=='A'){
                int idx=c[tti][ttj];
                //printf("zheli %d %d\n",tidx,idx);
                g[tidx][idx]=g[idx][tidx]=ts+1;
            }
        }
    }
}
int prim(){
    int ans=0;
    int Min=INF;
    int pos=1;
    _clr(used,false);
    _clr(low,0);
    used[pos]=true;
    for(int i=1;i<=cnt;i++){
        if(i!=pos){
            low[i]=g[pos][i];
        }
    }
    for(int i=1;i<cnt;i++){
        Min=INF;
        for(int j=1;j<=cnt;j++){
            if(!used[j] && low[j]<Min){
                Min=low[j];
                pos=j;
            }
        }
        used[pos]=true;
        ans+=Min;
        //printf("%d %d %d\n",Min,ans,pos);
        for(int j=1;j<=cnt;j++){
            if(!used[j] && low[j]>g[pos][j]){
                low[j]=g[pos][j];
            }
        }
    }
    return ans;
}
int main(void){
    //freopen("data.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        init();
        cnt=1;
        scanf("%d%d",&x,&y);
        getline(cin,mp[0]);
        for(int i=0;i<y;i++){
            getline(cin,mp[i]);
            //cout << mp[i] << endl;
            for(int j=0;j<x;j++){
                //printf("%c\n",mp[i][j]);
                if(mp[i][j]=='S' || mp[i][j]=='A'){
                    c[i][j]=cnt++;
                }
            }
        }
        cnt--;
        for(int i=0;i<y;i++){
            for(int j=0;j<x;j++){
                if(c[i][j]!=0){
                    _clr(vis,false);
                    bfs(i,j);
                }
            }
        }
        // for(int i=1;i<=cnt;i++){
        //     for(int j=1;j<=cnt;j++){
        //         printf("%d ",g[i][j]);
        //     }
        //     printf("\n");
        // }
        int ans=prim();
        printf("%d\n",ans);
    }
    return 0;
}
